package test;

public class 最长回文子串 {
        public static void main(String[] args) {
            String s = "babad";
            String longestPalindrome = findLongestPalindrome(s);
            System.out.println(longestPalindrome);
        }

        /**
         * 找到字符串 s 中最长的回文子串
         * @param s 待处理的字符串
         * @return 最长回文子串
         */
        public static String findLongestPalindrome(String s) {
            int len = s.length();
            if (len < 2) {
                return s;
            }
            int start = 0;  // 记录最长回文子串的起始位置
            int end = 0;    // 记录最长回文子串的结束位置

            for (int i = 0; i < len; i++) {
                int len1 = expandAroundCenter(s, i, i);    // 以 s[i] 为中心的回文子串长度
                int len2 = expandAroundCenter(s, i, i + 1);    // 以 s[i] 和 s[i+1] 为中心的回文子串长度
                int maxLen = Math.max(len1, len2);
                if (maxLen > end - start + 1) {
                    start = i - (maxLen - 1) / 2;
                    end = i + maxLen / 2;
                }
            }

            return s.substring(start, end + 1);
        }

        /**
         * 以 left 和 right 为中心，向左右扩展，找到最长的回文子串长度
         * @param s 待处理的字符串
         * @param left 左边界
         * @param right 右边界
         * @return 最长回文子串长度
         */
        public static int expandAroundCenter(String s, int left, int right) {
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            return right - left - 1;
        }

}
